#include "stdafx.h"

#define DO_INDEX
#define DO_PRINT
#define USE_MURMUR

// you will need google-sparsehash (http://code.google.com/p/google-sparsehash/) for dense_hash_map
#define USE_GOOGLE


#ifdef USE_GOOGLE
   #include <google\dense_hash_map>
   using namespace google;
#endif

using namespace std;

const string WORDCHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";

FILE * g_fin = stdin;
FILE * g_fout = stdout;

#ifdef USE_MURMUR
   unsigned int MurmurHash2 ( const void * key, int len, unsigned int seed );

   struct HashEnglishWords
   {
      enum { bucket_size = 4, min_buckets = 16384 };
      size_t operator()(const string& str) const
      {
         return MurmurHash2(str.c_str(), str.length(), 1);
      }

      bool operator()(const string& a, const string& b) const
      {
         return strcmp(a.c_str(), b.c_str()) < 0;
      }
   };
#endif

typedef vector<unsigned int> lines_list;

#ifdef USE_GOOGLE
   typedef dense_hash_map
#else
   typedef hash_map
#endif      
      <string
      , lines_list
#ifdef USE_MURMUR
      , HashEnglishWords
#endif
   > WordsIndex;

typedef map<string, const lines_list*> SortedWordsIndex;

const unsigned int BUFFER_SIZE = 4*1024*1024;
char buf[BUFFER_SIZE] = {};
char word_buf[128] = {};


inline int atoi_SimpleFast(char* str, int& result)
{
   if(str == 0) {result = 1; return 0;}

   int value = 0;
   char* cur = str;

   // we allow the number to start with + or -
   if(*cur == '+' || *cur == '-')
      cur++;

   result = !(*cur >= '0' && *cur <= '9');

   unsigned char digit;

   // we assume str ends with '\0'
   while ((digit = (*cur++^'0')) < 10)
      value = (value << 1) + (value << 3) + digit;

   if(*str == '-')
      value = -value;

   return value;
}


void parse(WordsIndex& wi)
{
   unsigned int line_number = 1;
   size_t bytes_read = 0, i = 0, iw = 0;
   bool inword = false;
#ifdef DO_INDEX
   string word;
#endif

   while(!feof(g_fin))
   {
      bytes_read = fread(buf, sizeof(char), BUFFER_SIZE - 1, g_fin);
      i = 0;

      while(i < bytes_read)
      {
         char& c = *(buf+i);

         if ((c>='A'&&c<='Z') || (c>='a'&&c<='z') || (c>='0'&&c<='9'))
         {
            if (c>='A'&&c<='Z') c -= 'A'-'a'; // tolower
            *(word_buf + iw++) = c; // accumulate word
            if(iw >= sizeof(word_buf)) iw = 1; // dirty hack, word buffer overrun protection
         }
         else if (iw)
         {
            *(word_buf+iw) = 0;

#ifdef DO_INDEX
            word.assign(word_buf, word_buf+iw);

            WordsIndex::mapped_type& v = wi[word];

            if(v.empty() || (v.back() != line_number))
            {
               v.push_back(line_number);
            }
#endif

            iw = 0;
         }

         if(c == 0x0a)
         {
            ++line_number;
         }

         i++;
      }
   }
}

void sort(const WordsIndex& wi, SortedWordsIndex& si)
{
   for (WordsIndex::const_iterator i = wi.begin(); i != wi.end(); ++i)
   {
      const string& word = i->first;
      const lines_list* lines = &(i->second);

      si.insert( make_pair(word, lines) );
   }
}

inline unsigned int wl(unsigned int ln)
{
   if(ln >= 1000000) return 7;
   if(ln >= 100000) return 6;
   if(ln >= 10000) return 5;
   if(ln >= 1000) return 4;
   if(ln >= 100) return 3;
   if(ln >= 10) return 2;
   return 1;
}

void print(const SortedWordsIndex& si)
{
   char *p = buf;

   for(SortedWordsIndex::const_iterator wp = si.begin(); wp != si.end(); ++wp)
   {
      const string& word = wp->first;
      const lines_list* lines = wp->second;

      fwrite(word.c_str(), 1, word.length(), g_fout);
      fwrite(" ", 1, 1, g_fout);

      p = buf;

      for(lines_list::const_iterator li = lines->begin(); li != lines->end(); ++li)
      {
         // line number for future use
         const unsigned int ln = *li;

         _itoa_s(ln, p, (buf+sizeof(buf)-p)-1, 10);

         p += wl(*li);
         *p++ = ',';
      }
      *p++ = '\n';

      fwrite(buf, 1, p - buf, g_fout);
   }
}

int _tmain(int argc, _TCHAR* argv[])
{
   WordsIndex wi;

#ifdef USE_GOOGLE
   wi.set_empty_key("_"); 
   wi.set_deleted_key("*");
#endif

   if (argc == 3)
   {
      _tfopen_s(&g_fin, argv[1], L"r");
      _tfopen_s(&g_fout, argv[2], L"w");
   }

   parse(wi);

#ifdef DO_PRINT
   SortedWordsIndex si;
   sort(wi, si);
   print(si);
#endif

   _fcloseall();

   return 0;
}

